package dp;

import java.util.Arrays;

public class CoinChange_322 {

    /**
     * 动态规划的问题都具有最优子结构，要符合「最优子结构」，子问题间必须互相独立。
     *
     * 如何列出正确的状态转移方程？
     * 1. 确定base case，目标金额 amount 为 0 时算法返回 0
     * 2. 确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。
     * 3. 确定选择，也就是导致「状态」产生变化的行为。
     * 4. 明确 dp 函数/数组的定义。dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。
     */
    public int coinChange(int[] coins, int amount) {
        // 定义dp数组，dp[n]表示输入一个金额n，返回凑出金额n的最少硬币数
        int[] dp = new int[amount + 1];
        // 凑成amount金额的硬币数最多只可能等于amount，所以初始化为 amount + 1 就相当于初始化为正无穷，
        Arrays.fill(dp, amount + 1);

        // base case
        dp[0] = 0;

        // 外层 for 循环在遍历所有状态的所有取值
        for (int i = 0; i < dp.length; i++) {
            // 遍历所有选择
            for (int coin : coins) {
                // dp[i]表示金额i的硬币数，当i<coin，说明凑不出来，跳过
                if (i - coin < 0) {
                    continue;
                }
                // dp[i]：因为有多种coin，每种coin对应的dp[i]不同，也需要从中选择最优值
                // dp[i-coin]+1 表示子问题，最后加1得到原问题的解
                // 动态规划都是原值与最优子结构的值进行比较
                dp[i] = Math.min(dp[i], dp[i-coin]+1);
            }
        }

        if (dp[amount] == amount + 1) {
            return -1;
        } else {
            return dp[amount];
        }
    }
}